package lc;
import java.util.*;
import org.junit.*;
public class Ex76 {
    class Solution {
        public String minWindow(String s, String t) {
            if (s.length() < t.length()) return "";
            int total = t.length(), len = s.length();
            char[] cs = s.toCharArray(), ts = t.toCharArray();
    
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < ts.length; i++) {
                map.put(ts[i], map.getOrDefault(ts[i], 0) + 1);
            }
            
            int lo = 0, hi = 0, tmp;
            String res = null;
            char c;
            while (hi < len) {
                while (hi < len && total > 0) {
                    c = cs[hi];
                    if (map.containsKey(c)) {
                        tmp = map.get(c);
                        if (tmp > 0)
                            total--;
                        map.put(c, tmp - 1);
    
                    }
                    hi++;
                }
    
                //移动左指针，以达到最短
                while (lo < hi) {
                    if (!map.containsKey(cs[lo])) {
                        lo++;
                    } else if ((tmp = map.get(cs[lo])) < 0) {
                        map.put(cs[lo], map.get(cs[lo]) + 1);
                        lo++;
                    } else {
                        break;
                    }
                }

                if (hi == len && total > 0) {
                    break;
                }
    
                //更新最短长度，并移动左指针进入下轮循环
                if (res == null || (tmp = hi - lo) < res.length()) {
                    res = s.substring(lo, hi);
                }
                map.put(cs[lo], map.get(cs[lo]) + 1);
                total++;
                lo++;
            }
            return res == null ? "" : res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        // String str = "ADOBECODEBANC", t = "ABC";
        String str = "A", t = "B";
        System.out.println(s.minWindow(str, t));;
    }

    @Test
    public void tes2t() {
        Solution2 s = new Solution2();
        String str = "ADOBECODEBANC", t = "ABC";
        // String str = "A", t = "B";
        System.out.println(s.minWindow(str, t));;
    }


    class Solution2 {
        public String minWindow(String s, String t1) {
            Map<Character, Integer> map = new HashMap<>();
            int cnt = t1.length(), n = s.length(), min = Integer.MAX_VALUE, start = 0, end = 0;
            String res = null;
            char[] ss = s.toCharArray(), ts = t1.toCharArray();
            for (char c: ts) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
    
            while (end < n) {
                while (end < n && cnt > 0) {
                    if (map.containsKey(ss[end])) {
                        int t  = map.get(ss[end]);
                        map.put(ss[end], t - 1);
                        if (t > 0) {
                            cnt--;
                        }
                    }
                    end++;
                    if (cnt == 0) {
                        break;
                    }
                }
                //移动左指针，使得最优
                int t;
                while (start < end) {
                    //!map.containsKey(ss[start]) || (t = map.get(ss[start]) < 0)
                    if (!map.containsKey(ss[start])) {
                        start++;
                    } else if ((t = map.get(ss[start])) < 0) {
                        map.put(ss[start], t + 1);
                        start++;
                    } else {
                        t = end - start;
                        if (t < min) {
                            min = t;
                            res = new String(ss, start, min);
                        }
                        map.put(ss[start], map.get(ss[start]) + 1);
                        start++;
                        cnt++;
                        break;
                    }
                }
            }
            // if (len - start < min) 
            return res == null ? "" : res;
        }
    }
}
